package jianzhi_offer;

import java.util.PriorityQueue;

/**
 * @author: zhouyang
 * @descrpition:
 * @time: 2019-04-16 20:47
 */
public class _62_数据流中的中位数 {
    private int count = 0;
    private PriorityQueue<Integer> min = new PriorityQueue<>();
    private PriorityQueue<Integer> max = new PriorityQueue<>((o1,o2)->o2-o1);

    public void Insert(Integer num) {
        count++;
        if ((count & 1) == 0) { // 判断偶数的高效写法
            if (!max.isEmpty() && num < max.peek()) {
                max.offer(num);
                num = max.poll();
            }
            min.offer(num);
        } else {
            if (!min.isEmpty() && num > min.peek()) {
                min.offer(num);
                num = min.poll();
            }
            max.offer(num);
        }
    }

    public Double GetMedian() {
        if(count==0)
            throw new RuntimeException("no available number!");
        double result;
        //总数为奇数时，大顶堆堆顶就是中位数
        if((count&1)==1)
            result=max.peek();
        else
            result=(min.peek()+max.peek())/2.0;
        return result;
    }
}
